import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:给出一个字符串数组 words 组成的一本英语词典。返回 words 中最长的一个单词，
 * 该单词是由 words 词典中其他单词逐步添加一个字母组成。
 *
 * 若其中有多个可行的答案，则返回答案中字典序最小的单词。若无答案，则返回空字符串。
 *
 * 请注意，单词应该从左到右构建，每个额外的字符都添加到前一个单词的结尾。
 * User: wangxin
 * Date: 2025-03-27
 * Time: 21:06
 */
public class Test {
    public static String longestWord(String[] words) {
        Arrays.sort(words,(a, b)->{
            if(a.length() != b.length()){
                return a.length() - b.length();
            }else{
                return b.compareTo(a);
            }
        });
        String res = "";
        Set<String> set = new HashSet<>();
        set.add("");
        int n = words.length;
        for(int i = 0;i < n;i++){
            String word = words[i];
            if(set.contains(word.substring(0,word.length() - 1))){
                set.add(word);
                res = word;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        String[] words = {"a", "banana", "app", "appl", "ap", "apply", "apple"};
        longestWord(words);
        Deque<Integer> queue = new LinkedList<>();
    }
}
